package bracket;

import java.util.Deque;
import java.util.LinkedList;

public class Solution {

    //构造函数
    public Solution() {
    }
    //lc20
    public boolean isValid1(String s) {
        Deque<Character> stack=new LinkedList<Character>();
        if(s.length() % 2 != 0){
            return false;
        }
        for(int i=0 ;i<s.length();i++){
            //取出位置的字符
            Character c = s.charAt(i);
            if(c == '(' || c == '{' || c == '[')
                stack.push(c);
            else{
                if(!stack.isEmpty()&&leftOf(c) == stack.peek()){
                    stack.pop();
                }
                else
                    //不匹配
                    return false;
            }
        }
        //看他是不是空
        return stack.isEmpty();
    }
    char leftOf(char c){
        if(c==')') return '(';
        if(c=='}') return '{';
        return '[';
    }
    //lc921 使括号的最小添加
    public int minAddToMakeValid(String s){
        //res 记录左边插入次数
        int res = 0;
        //need 右边括号需求量
        int need = 0;
        for (int i=0;i<s.length();i++){
            //如果匹配到一个左括号
            if(s.charAt(i) == '('){
                need++;
            }
            if(s.charAt(i)==')'){
                need--;
                if(need==-1){
                    //将need赋值为0
                    need = 0;
                    //需要一个左括号
                    res++;
                }
            }
        }
        //返回左右括号之和
        return res+need;
    }
    //lc 1541 (()平衡字符串
    public int minInsertions(String s){
        //对右括号的需求量
        int need = 0;
        //插入的括号数
        int res = 0;
        for(int i=0;i<s.length();i++){
            if(s.charAt(i) == '('){
                need = need + 2;
                if(need%2==1){
                    //右插入加一
                    res++;
                    //需求减一
                    need--;
                }
            }
            if(s.charAt(i) == ')'){
               need = need-1;
               //出现这种情况就是右边太少了 要补一个左 所以 -1+2 = 1 need=1
               if(need==-1){
                   need=1;
                   //插入左边
                   res++;
               }
            }
        }
        return res+need;
    }
}
